A $(1 + {\varepsilon})$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

摘要

Graphs with bounded highway dimension were introduced by Abraham et al. [SODA2010] as a model of transportation networks. We show that any such graph can beembedded into a distribution over bounded treewidth graphs with arbitrarilysmall distortion. More concretely, given a weighted graph G = (V, E) ofconstant highway dimension, we show how to randomly compute a weighted graph H= (V, E') that distorts shortest path distances of G by at most a 1 +${\varepsilon}$ factor in expectation, and whose treewidth is polylogarithmicin the aspect ratio of G. Our probabilistic embedding implies quasi-polynomialtime approximation schemes for a number of optimization problems that naturallyarise in transportation networks, including Travelling Salesman, Steiner Tree,and Facility Location. To construct our embedding for low highway dimension graphs we extendTalwar's [STOC 2004] embedding of low doubling dimension metrics into boundedtreewidth graphs, which generalizes known results for Euclidean metrics. We addseveral non-trivial ingredients to Talwar's techniques, and in particularthoroughly analyse the structure of low highway dimension graphs. Thus wedemonstrate that the geometric toolkit used for Euclidean metrics extendsbeyond the class of low doubling metrics.